Some authentication methods for performing authentication using only passwords have been proposed so far. These authentication methods include a method that allows a dictionary attack of a password by communication eavesdropping of an attacker. In order to achieve higher security, it is preferable for an authentication method using only a password to have resistances against every kind of attack (for example, communication eavesdropping, replay attack, message alteration, spoofing, and man-in-the-middle attack) on a public network such as the Internet. In order to meet such requirements, an authentication method, which has foundation of security in a discrete logarithm problem, and is secure against not only every kind of attack on the public network but also a KCI (Key Compromise Impersonation) attack in which an attacker spoofs a client using recorded information of a server, is known. However, a problem of a conventional authentication method having such security lies in that both a client and server cannot minimize calculation amounts (the number of modulo exponentiation times). On the client side, since a user terminal is often a compact, slow device, a personal computer of an older generation, a smart card, or a personal digital assistance (PDA), it is desirable to suppress the amount of calculation as much as possible. On the server side, a very large number of users have to be managed, and the calculation capability of the server is often not very high. Hence, it is also desired that the calculation amount is as low as possible.
In a method described in PLT1, mutual authentication is securely done via a data network between two parties who share only a password using Diffie-Hellman key exchange. However, an embodiment shown in FIGS. 2 and 3 of PLT1 is not secure against a KCI attack. An embodiment using a password verifier shown in FIGS. 4 and 5 is secure against a KCI attack, but both a client and server require larger calculation amounts than an authentication method proposed by the present inventors.
A method described in PLT2 is that which improves the calculation efficiency of the method described in FIG. 2 of PLT1, and can at least halve the calculation amount on the client side. However, this method is not secure against a KCI attack. In order to assure security against a KCI attack, the method of PLT2 can be modified like the method described in PLT1 (the embodiment using the password verifier shown in FIGS. 4 and 5), but both a client and server require more calculation amounts than the authentication method proposed by the present inventors.
In a method described in PLT3, a terminal and authentication server share a password and encryption key in advance, the terminal performs authentication by encrypting the password using the encryption key, and sending the encrypted password to the authentication server, and when the authentication has succeeded, the terminal and server exchange an encryption key for a data communication by a conventional method. However, the terminal requires a tamper resistance of a device so as to securely save the encryption key. When the encryption key leaks, the password can be extracted from previously communicated ciphertext. That is, the security is lower than the authentication method proposed by the present inventors.